package com.agile.leetcode.easy.minSubarray;


import java.math.BigInteger;
import java.util.Arrays;

/**
 * 1590. 使数组和能被 P 整除
 * 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
 *
 * 请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
 *
 * 子数组 定义为原数组中连续的一组元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [3,1,4,2], p = 6
 * 输出：1
 * 解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
 * 示例 2：
 *
 * 输入：nums = [6,3,5,2], p = 9
 * 输出：2
 * 解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
 * 示例 3：
 *
 * 输入：nums = [1,2,3], p = 3
 * 输出：0
 * 解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。
 * 示例  4：
 *
 * 输入：nums = [1,2,3], p = 7
 * 输出：-1
 * 解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。
 * @Author:ChenZhangKun
 * @Date: 2021/4/1 10:43
 */
public class MinSubarray {
    public static void main(String[] args) {
        int[] nums={1000000000,1000000000,1000000000};
        MinSubarray subarray=new MinSubarray();
        int i = subarray.minSubarray(nums, 3);
        System.out.println(i);
    }
    public int minSubarray(int[] nums, int p) {
        // 得到数组综合
        BigInteger sum = count(nums);
        if (sum.mod(new BigInteger(p+"")).equals(new BigInteger("0"))) return 0;
        if (sum.compareTo(new BigInteger(p+""))<0) return -1;
        // 拿到数组长度
        int length = nums.length;
        // 最多移除length-1个元素
        for (int i = 1; i < length; i++) {
            // 每次移除i个元素
            if (isAliquot(nums,p,i)) return i;
        }
        return -1;
    }

    /**
     * 是否能被整除
     * @param nums
     * @param p
     * @param i
     * @return
     */
    public boolean isAliquot(int[] nums, int p, int i) {
        // 复制数组
        int[] copy = Arrays.copyOf(nums, nums.length);
        // 数组转换为集合
        for (int j = 0; j < nums.length; j++) {
            for (int m = 0; m < i; m++) {
                // 防止指针越界
                if (j+m<copy.length){
                    // 置为0
                    copy[j+m]=0;
                }
            }
            // 重新计算
            BigInteger count = count(copy);
            if (count.mod(new BigInteger(p+"")).equals(new BigInteger("0"))) return true;
            // 恢复数组
            copy=Arrays.copyOf(nums,nums.length);
        }
        return false;
    }

    /**
     * 计算数组的和
     * @param nums
     * @return
     */
    public BigInteger count(int[] nums) {
        BigInteger integer=new BigInteger("0");
        for (int num : nums) {
            integer=integer.add(new BigInteger(num+""));
        }
        return integer;
    }
}
